package com.xiaolin.algorithm.sort;

import java.util.Arrays;

/**
 * @ClassName CountSort
 * @Description 计数排序
 * @Detail detail
 * @Author MyPC
 * @Date 2020/11/4
 * @Version 1.0
 */
public class CountSort {

    public static void main(String[] args) {
        int arr[]={3,2,4,8,8,1,5,9,200};
        int[] sort = sort(arr);
        System.out.println(Arrays.toString(sort));
    }


    public static int[] sort(int[] arr){
        if(arr.length==0){
            return null;
        }
        // 1、获取新数组的长度,初始化一个临时数组
        int min = getMin(arr);
        int newArrLength = getNewArrLength(arr);
        int[] tempArr=new int[newArrLength];
        // 2、将数据存入新数组
        for(int i=0;i<arr.length;i++){
            // 算出元素存入的索引位置
            int index = arr[i] - min;
            // 存入元素到相应的所索引位置
            tempArr[index]=++tempArr[index];
        }
        //3、排序
        int[] newArr=new int[arr.length];
        int index=0;
        for(int i=0;i<tempArr.length;i++){
            if(tempArr[i]==0){
                // 如果索引下没有元素存储，那么直接跳过本次循环
                continue;
            }
            for(int j=0;j<tempArr[i];j++){
                // 计算出原来的值，并存入新数组
                newArr[index++]=min+i;
            }
        }
        return newArr;
    }

    /**
     * 获取新数组的初始化长度
     * @param arr
     * @return
     */
    private static int getNewArrLength(int[] arr){
        return getMax(arr)-getMin(arr)+1;
    }

    /**
     * 获取最大值
     * @param arr
     * @return
     */
    private static int getMin(int[] arr){
        // 1、遍历数组
        int min=arr[0];
        for (int i=1;i<arr.length;i++){
            if(min>arr[i]){
                min=arr[i];
            }
        }
        return min;
    }

    /**
     * 获取最小值
     * @param arr
     * @return
     */
    private static int getMax(int[] arr){
        // 1、遍历数组
        int max=arr[0];
        for (int i=1;i<arr.length;i++){
            if(max<arr[i]){
                max=arr[i];
            }
        }
        return max;
    }

}
